package com.mlh.stack;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author 缪林辉
 * @date 2024/3/21 13:26
 * @DESCRIPTION
 */

// 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
// 有效字符串需满足：
// 左括号必须用相同类型的右括号闭合。
// 左括号必须以正确的顺序闭合。
// 每个右括号都有一个对应的相同类型的左括号。
//    {[}] 这个不是有效字符串

// 思路:就是遇到左括号入栈  遇到右括号和栈顶对比 看看是不是一对,不是一对或者栈为空 直接false
// 全部判断完 栈为空才返回true
public class 有效的括号 {
    public boolean method1(String s) {
        Stack<Character> stack=new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char temp=s.charAt(i);
            if(temp=='{'||temp=='('||temp=='['){
                stack.push(temp);
            }else {
                //这个判空可以优化
                //往栈中先加入一个元素
                //这样就不需要判空了,不过满足要求的字符串最终栈会有一个元素
                //边界条件需要改变
                if(stack.empty()){
                    return false;
                }
                switch (temp){
                    case '}':
                        if(stack.pop()!='{'){
                            return false;
                        }
                        break;
                    case ')':
                        if(stack.pop()!='('){
                            return false;
                        }
                        break;
                    case ']':
                        if(stack.pop()!='['){
                            return false;
                        }
                        break;
                }
            }
        }
        return stack.empty();
    }

    public boolean practice(String s) {
        if(s.length()%2!=0){//长度不为偶数肯定不会是有效的
            return false;
        }
        //将成对的括号放入map中，方便判断
        HashMap<Character,Character>map=new HashMap<>();
        map.put(']','[');
        map.put('}','{');
        map.put(')','(');
        LinkedList<Character>stack=new LinkedList<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            Character a = map.getOrDefault(chars[i], 'a');
            if(a=='a'){
                stack.push(chars[i]);
            }else{
                if(a!=stack.peek()){
                    return false;
                }
                stack.pop();
            }
        }
        return stack.isEmpty();
    }

    public static boolean practice2(String s) {
        char[] chars = s.toCharArray();
        LinkedList<Character>stack=new LinkedList<>();
        HashMap<Character,Character> map =new HashMap<>();
        map.put(')','(');
        map.put('}','{');
        map.put(']','[');
        for (int i = 0; i < chars.length; i++) {
            Character a = map.getOrDefault(chars[i], 'a');
            if(a=='a'){
                stack.push(chars[i]);
            }else{
                if(stack.peek()!=a){
                    return false;
                }
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}
